Menurut legenda yang tercatat dalam Samguk Yusa yang ditulis pada abad ke-13, pada tahun 42 M, enam biji telur turun dari syurga dengan pesanan bahawa mereka akan menjadi raja. Enam orang budak lelaki dilahirkan, dan dalam masa 12 hari mereka menjadi dewasa. Salah satunya, bernama Suro, menjadi raja Geumgwan Gaya, dan lima yang lain mengasaskan lima Gaya yang lain, iaitu Daegaya, Seongsan Gaya, Ara Gaya, Goryeong Gaya, dan Sogaya.[9]

Tatanegara Gaya berkembang daripada struktur politik utama dua belas buah suku konfederasi Byeonhan kuno, salah satu konfederasi Samhan. Ketua-ketua yang tersusun secara kasar dibentuk menjadi enam kumpulan Gaya, yang berpusat di Geumgwan Gaya. Atas dasar sumber arkeologi dan catatan bertulis yang terhad, para sarjana seperti Sin telah mengenal pasti bahawa akhir abad ke-3 sebagai masa peralihan dari Byeonhan ke Gaya, dengan peningkatan aktiviti ketenteraan dan mengubah adat penguburan.[10] Sin[11] selanjutnya berpendapat bahawa ini dikaitkan dengan penggantian elit sebelumnya di beberapa kerajaan (termasuk Daegaya) oleh unsur-unsur dari kerajaan Buyeo, yang membawa ideologi dan gaya pemerintahan yang lebih ketenteraan.

Konfederasi Gaya hancur di bawah tekanan dari Goguryeo antara tahun 391 dan 412 M, walaupun pemerintahan Gaya terakhir tetap merdeka sehingga mereka ditakluki oleh Silla pada tahun 562, sebagai hukuman kerana menolong Baekje dalam perang melawan Silla.